#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣300. 最长递增子序列
// 【难度】中等
// 【提交】2025.10.21 https://leetcode.cn/problems/longest-increasing-subsequence/submissions/
// 【标签】动态规划；二分查找
class Solution_LC0300 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp;
        int ans = 1;
        for(auto i : nums) {
            auto it = ranges::lower_bound(dp, i);
            if(it == dp.end()) dp.push_back(i);
            else *it = i;
        }
        return dp.size();
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums，找到其中最长严格递增子序列的长度。
 * 模型：动态规划+二分查找，通过维护一个递增序列来优化求解过程。
 * 
 * 二、标准解法状态设计
 * 使用贪心+二分查找的方法：
 * 1. 维护一个dp数组，其中dp[i]表示长度为i+1的递增子序列的末尾元素的最小值
 * 2. 遍历数组，对于每个元素，使用二分查找在dp数组中找到第一个大于等于该元素的位置
 * 3. 如果找到，替换该位置的元素；如果没找到，将元素添加到dp数组末尾
 * 4. 最终dp数组的长度即为最长递增子序列的长度
 * 
 * 三、你的实现思路
 * 使用C++20的ranges::lower_bound进行二分查找，维护一个递增序列。
 * 通过不断更新序列中的元素，保证序列长度的最大化。
 * 
 * 四、复杂度
 * 时间：O(n log n)，每个元素需要O(log n)时间进行二分查找。
 * 空间：O(n)，需要dp数组存储中间结果。
 * 
 * 五、优缺点分析
 * 优点：
 *   - 时间复杂度低，比O(n²)的DP解法更高效；
 *   - 代码简洁，实现优雅。
 * 缺点：
 *   - 无法直接获取最长递增子序列的具体内容；
 *   - 需要C++20支持（ranges::lower_bound）。
 * 
 * 六、改进建议
 * 1. 可以使用标准库的lower_bound替代ranges::lower_bound以提高兼容性；
 * 2. 可以添加输入验证：if (nums.empty()) return 0;
 * 3. 可以扩展算法以记录具体的最长递增子序列。
 * 
 * 七、一句话总结
 * 贪心+二分查找是解决最长递增子序列问题的高效方法，你的实现简洁且高效。
 */